from typing import List, Tuple


def bag_max_weight_v2(items_info: List[int], capacity: int) ->int:
    """
    固定容量背包，计算放进背包的最大重量
    使用1维素组 mem[capacity]备忘录
    :param items_info:物品重量
    :param capacity:背包容量
    :return:
    """
    n = len(items_info)
    mem = [False] * (capacity+1)
    # 处理第一个物品
    mem[0] = True
    if items_info[0] <= capacity:
        mem[items_info[0]] = True

    for i in range(1, n):
        #把第i个物品放入背包
        for cur_weight in range(capacity-items_info[i], -1, -1):
            if mem[cur_weight]:
                mem[cur_weight + items_info[i]] = True
    for w in range(capacity, -1, -1):
        if mem[w]:
            return w
    return 0


def bag_max_weight(items_info: List[int], capacity: int) ->int:
    """
    固定容量背包，计算放进背包的最大重量
    使用二维素组 mem[n, capacity]备忘录
    :param items_info:物品重量
    :param capacity:背包容量
    :return:最大装置重量
    """
    n = len(items_info)
    mem = [[False]*(capacity+1) for i in range(n)]

    mem[0][0] = True # 第一行数据特殊处理
    if items_info[0] <= capacity:
        mem[0][items_info[0]] = True

    for i in range(1, n):
        for cur_weight in range(capacity+1):
            if mem[i-1][cur_weight]:
                mem[i][cur_weight] = mem[i-1][cur_weight]  # 不选
                if cur_weight + items_info[i] <= capacity: # 选
                    mem[i][cur_weight + items_info[i]] = True

    for w in range(capacity, -1, -1):
        if mem[-1][w]:
            return w
    return 0


def bag_max_value(items_info: List[int], capacity: int) ->int:
    """
    固定容量背包，计算放进背包的最大价值
    使用二维素组 mem[n, capacity]备忘录 存储最大价值

    mem[i][j] 将前i个物品放入限重为j背包可得到的最大价值, 0<=i<=n, 0<=j<=capacity

    第i个舞物品不放入背包：即为mem[i-1][j]
    w,v = items_info[i]
    放入背包：mem[i-1][j-w] + v

    状态转移方程：
    mem[i][j] = max(mem[i-1][j], mem[i-1][j-w]+v)
    :param items_info:物品[重量,价值]
    :param capacity:背包容量
    :return:最大装置价值
    """
    n = len(items_info)
    memo = [[0] * (capacity + 1) for i in range(n + 1)]

    for i in range(1, n+1):
        w, v = items_info[i-1]
        for j in range(1, capacity + 1):
            if j < w: # 不放入
                memo[i][j] = memo[i-1][j]
            else: # 放入
                memo[i][j] = max(memo[i-1][j], memo[i-1][j-w] + v)
    return max(memo[-1])


def bag_max_value_v2(items_info: List[int], capacity: int) ->int:
    """
    固定容量背包，计算放进背包的最大价值
    使用1维素组 mem[capacity]备忘录 存储最大价值

    mem[i][j] 只跟dp[i-1][0,...,j-1]有关，即可采用滚动数组（去掉第一维）
    逆向循环

    :param items_info:物品[重量,价值]
    :param capacity:背包容量
    :return:最大装置价值
    """
    n = len(items_info)
    mem = [0]*(capacity+1)

    for i in range(1, n+1):
        w, v = items_info[i-1]
        for j in range(capacity, w-1, -1):
            mem[j] = max(mem[j], mem[j-w] + v)
    return max(mem)


def test_bag_max_weight():
    items_info = [9,34,7,12,8,7]
    capacity = 65
    print("物品重量：{}, 背包容量：{}".format(items_info, capacity))
    print("可放进背包最大重量: ", bag_max_weight(items_info, capacity))


def test_bag_max_weight_v2():
    items_info = [9,34,7,12,8,7]
    capacity = 65
    print("物品重量：{}, 背包容量：{}".format(items_info, capacity))
    print("可放进背包最大重量: ", bag_max_weight_v2(items_info, capacity))


def test_bag_max_value():
    items_info = [(3, 5), (2, 2), (1, 4), (1, 2), (4, 10)]
    capacity = 9
    print("物品重量：{}, 背包容量：{}".format(items_info, capacity))
    print("可放进背包最大价值: ", bag_max_value(items_info, capacity))


def test_bag_max_value_v2():
    items_info = [(3, 5), (2, 2), (1, 4), (1, 2), (4, 10)]
    capacity = 9
    print("物品重量：{}, 背包容量：{}".format(items_info, capacity))
    print("可放进背包最大价值: ", bag_max_value_v2(items_info, capacity))


if __name__ == '__main__':
    test_bag_max_weight()
    test_bag_max_weight_v2()
    test_bag_max_value()
    test_bag_max_value_v2()

